The addition of two N-bit operands to form an N-bit result, often called "carry propagate addition", is a fundamental operation in digital processors. A variety of techniques have been developed to perform this operation.
A simple method for performing carry propagate addition is the ripple adder. The ripple adder requires relatively few transistors per bit, but it is usually a relatively slow technique. The ripple adder is thus the technique against which other methods are often measured.
FIG. 1 shows a typical ripple adder cell. A(i) and B(i) are individual bits of the two operands to be added, Cin(i) is the carry-in signal from the prior adder cell, Cout(i) is the carry-out signal from the present cell, and Sum(i) is the sum signal of the present cell. The carry-out signal of one cell is the carry-in signal to the next cell. Table 1, shown as a PASCAL-like language program, summarizes the Boolean equations for the ripple adder method, where "+" is the Boolean "OR", "*" is the Boolean "AND", and "XOR" is the Boolean "Exclusive-OR":
TABLE 1 ______________________________________ For i = 0 through N-1 (N bit adder) DO BEGIN K(i) = A(i) + B(i) G(i) = A(i) * B(i) P(i) = A(i) XOR B(i) Cout(i) = G(i) + [K(i) * Cin(i)] = Cin(i+1) Sum(i) = P(i) XOR Cin(i) End ______________________________________
The ripple adder may be sped up with the addition of "carry look ahead" circuitry. To implement a carry look ahead adder, the ripple adder cells are organized into blocks of, for example, four ripple adder cells. Each block of four ripple adder cells as shown in FIG. 2 is provided with additional gates which allow carry propagation across the entire block if the "K" bits are all 1 (i.e., the outputs of the OR gates K(i)). The carry look ahead adder is moderately fast and is economical to implement in MOS circuitry.
Another scheme is the "conditional sum" adder reported by Sklansky, "Conditional-Sum Addition Logic", I.R.E. Transactions on Electronic Computers, page 226, June 1960. Although very fast in operation, conditional sum addition takes far more logic to implement than the other, slower techniques discussed above. The result is that conditinal sum addition has a very high cost per bit. In practice, this technique has not enjoyed widespread usage.
Thus, several methods for performing N-bit addition have been used in the prior art. However, these known methods are often either too slow for the new generations of computers or they are substantially more complex and costly than is desirable.